package com.liang.leetcode.string;

import java.util.Arrays;

/**
 * 28.找出字符串中第一个匹配项的下标
 * 实现 strStr() 函数。
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 * 示例 1: 
 *  输入: haystack = "hello", needle = "ll" 
 *  输出: 2
 * 示例 2: 
 *  输入: haystack = "aaaaa", needle = "bba" 
 *  输出: -1
 *
 * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
 */
public class String04_StrStr {
    public static void main(String[] args) {
        String haystack = "leetcode";
        String needle = "leeto";
        int index = strStr(haystack, needle);
        System.out.println(index);
    }

    /**
     * 解法一：调用函数
     */
    public static int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    /**
     * 解法二：暴力循环求解
     * 转为字符数组
     */
    public static int strStr2(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        char[] s = haystack.toCharArray(), p = needle.toCharArray();
        // 循环匹配：保证 n 能全部容纳 m（避免数组越界）
        for (int i = 0; i < n - m + 1; i++) {
            int a = i, b = 0;
            // 循环检查 needle 是否在当前位置开始匹配
            while (b < m && s[a] == p[b]) {
                // 如果当前字符匹配，则移动指针
                a++;
                b++;
            }
            // 如果 b 等于 m，说明 needle 已经完全匹配，返回当前位置 i
            if (b == m) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 暴力循环求解：不转为字符数组
     */
    public static int strStr3(String haystack, String needle) {
        // 获取主字符串和子字符串的长度
        int n = haystack.length(), m = needle.length();
        // 遍历主字符串，寻找子字符串
        for (int i = 0; i < n - m + 1; i++) {
            // 假设找到了子字符串
            boolean flag = true;
            // 检查当前位置开始的子串是否与目标子字符串匹配
            // 循环正常结束表示子串全部匹配成功，即不跳出循环
            for (int j = 0; j < m; j++) {
                // 如果字符不匹配，则标记为未找到，并跳出循环
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            // 如果标记为找到，则返回当前位置作为子字符串的起始位置
            if (flag) {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * KMP 求解
     */
    public static int strStr4(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }
        // next 数组
        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return (i - needle.length() + 1);
            }
        }
        return -1;
    }

    /**
     * 求模式串的 next 数组
     * @param next next数组
     * @param s 模式串
     */
    // 模式串 aabaaf 的 next 数组为 [0, 1, 0, 1, 2, 0]
    public static void getNext(int[] next, String s) {
        // 1.初始化：定义两个指针i和j，j指向前缀末尾位置[0,j]，i指向后缀末尾位置[1,i]
        int j = 0;
        // next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）
        next[0] = j;
        // 因为j初始化为-1，那么i就从1开始，进行s[i] 与 s[j+1]的比较。
        // 循环求i下标字符的最长相等的前后缀长度，从第二个字符开始
        // 看成遍历文本串 [1,i]后缀，比对模式串[0,j]前缀
        for (int i = 1; i < s.length(); i++) {
            // j 既表示前缀末尾下标，又表示前缀 [0,j] 和 [1,i] 后缀的最长相等前后缀的长度
            // 比较前后缀最后一个字符是否相等：s.charAt(i) 获取后缀的最后一个字符，s.charAt(j) 获取前缀的最后一个字符
            // 2.处理前后缀不相同的情况 => 需要回退，j回退到0的位置后便无法回退
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1]; //为什么回退到j-1，，【i=1,j=0、i=2,j=1 j=0、i=3,j=0 、i=4,j=1、i=5,j=2 j=1 j=0】
            }
            // 3.处理前后缀相同的情况 => 长度+1
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            // 4.更新next数组
            next[i] = j; // [0, 1, 0, 1, 2, 0]
        }
        System.out.println(Arrays.toString(next));
    }
}
